package list;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode234 {
    public static void main(String[] args) {
        int[] head_array = {1,2,3,4,2,1};
        ListNode head = createListNode(head_array);
        System.out.println(isPalindrome2(head));
    }

    private static ListNode createListNode(int[] nums){
        ListNode head = new ListNode(nums[0]);
        ListNode current = head;
        for (int i = 1; i < nums.length; i++) {
            ListNode temp = new ListNode(nums[i]);
            current.next = temp;
            current = current.next;
        }
        return head;
    }

    public static boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        int length = 0;
        ListNode cur = head;
        ArrayList<Integer> arrayList = new ArrayList<>();
        while(cur!=null){
            arrayList.add(cur.val);
            cur = cur.next;
            length++;
        }
        if (length == 1) return true;
        if(length%2==0){
            int right = length/2;
            int left = right-1;
            while(left >= 0){
                if(arrayList.get(left) != arrayList.get(right)) return false;
                left--;
                right++;
            }
            return true;
        }
        else {
            int num = length/2;
            int right = num+1;
            int left = num-1;
            while(left >= 0){
                if(arrayList.get(left) != arrayList.get(right)) return false;
                left--;
                right++;
            }
            return true;
        }
    }

    public static boolean isPalindrome2(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode secondhalf = reverse(slow);
        ListNode firsthalf = head;
        while(secondhalf != null){
            if(secondhalf.val != firsthalf.val) return false;
            secondhalf = secondhalf.next;
            firsthalf = firsthalf.next;
        }
        return true;
    }

    public static ListNode reverse(ListNode head){
        ListNode prev = null;
        while (head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}
